package leetcode;

import java.util.HashSet;

/**
 * description:
 * author:zt
 * date:2021-07-30
 */

/**
 * 给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
 *
 * 若无答案，则返回空字符串。
 */
public class leetcode720 {
    public String longestWord(String[] words) {
        String ans = "";
        HashSet<String> set = new HashSet<>();
        for (String word : words) set.add(word);
        for (String word : words) {
            if (word.length()> ans.length() || word.length()==ans.length()&&word.compareTo(ans)<0){
                boolean check = true;
                for (int i = 1; i < word.length(); i++) {
                    if (!set.contains(word.substring(0,i))){
                        check = false;
                        break;
                    }
                }
                if (check) ans = word;
            }
        }
        return ans;
    }
}
